/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName   : Leetcode022 
 * @author      : ganwei 
 * @date        : 2020年5月4日
 * @Description : Leetcode022
 */
public class Leetcode0022 {
	
	private List<String> result = new ArrayList<String>();
	/**
	 * -解题思路，回溯算法
	 */
    public List<String> generateParenthesis(int n) {
    	if(n<=0) {
    		return result;
    	}
    	StringBuilder sb = new StringBuilder();
    	backtrack(n,n,sb);
    	return result;
    }
    /**
     * -回溯函数主题,套用回溯算法框架
     */
    public void backtrack(int left,int right,StringBuilder sb) {
    	if(right < left) {
    		return;
    	}
    	if(left < 0 || right < 0) {
    		return;
    	}
    	if(left == 0 && right == 0) {
    		result.add(sb.toString());
    	}
    	
    	sb.append('(');
    	backtrack(left-1,right,sb);
    	sb.deleteCharAt(sb.length()-1);
    	
    	sb.append(')');
    	backtrack(left,right-1,sb);
    	sb.deleteCharAt(sb.length()-1);
    	
    }

    public static void main(String[] args){
    	
    }
}
